package P1线性结构;
//中缀表达式计算器
public class InfixCalculator {
    public static void main(String[] args) {
        String expression = "2+2*2/2*(2+2*2*(2-2*2*2)/2+2-2*2)/2+(2+2*2)/2-2";
        int result = evalue(expression);
        System.out.println(result);
        System.out.println(2+2*2/2*(2+2*2*(2-2*2*2)/2+2-2*2)/2+(2+2*2)/2-2);
    }

    private static int evalue(String expression) {
        expression = format(expression);
        String[] tokens = expression.split(" ");
        //数字栈
        LinkedList<Integer> numberStack = new LinkedList<>();
        //操作符栈
        LinkedList<String> operatorStack = new LinkedList<>();
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].length() != 0) {  //空串的过滤
                String token = tokens[i];
                if (token.equals("+") || token.equals("-")) {
                    //什么时候出栈进行计算？栈不为空且栈顶不为( -> 栈顶是+-*/
                    while (!operatorStack.isEmpty() && !operatorStack.peek().equals("(")) {
                        process(numberStack, operatorStack);
                    }
                    //什么时候直接进栈？栈为空 栈不为空栈顶为(
                    operatorStack.push(token);
                } else if (token.equals("*") || token.equals("/")) {
                    //什么时候出栈进行计算？栈不为空且栈顶为*/
                    while (!operatorStack.isEmpty() && (operatorStack.peek().equals("*") || operatorStack.peek().equals("/"))) {
                        process(numberStack, operatorStack);
                    }
                    //什么时候直接进栈？栈为空 栈不为空栈顶为( 栈不为空栈顶为+-
                    operatorStack.push(token);
                } else if (token.equals("(")) {
                    operatorStack.push("(");
                } else if (token.equals(")")) {
                    //只要当前栈顶不是(
                    while (!operatorStack.peek().equals("(")) {
                        process(numberStack, operatorStack);
                    }
                    operatorStack.pop();
                } else {//数字字符串
                    numberStack.push(Integer.parseInt(token));
                }
            }
        }
        //处理剩下的操作符和数字
        while (!operatorStack.isEmpty()) {
            process(numberStack, operatorStack);
        }
        return numberStack.pop();
    }

    private static void process(LinkedList<Integer> numberStack, LinkedList<String> operatorStack) {
        int num1 = numberStack.pop();
        int num2 = numberStack.pop();
        String op = operatorStack.pop();
        if (op.equals("+")) {
            numberStack.push(num2 + num1);
        } else if (op.equals("-")) {
            numberStack.push(num2 - num1);
        } else if (op.equals("*")) {
            numberStack.push(num2 * num1);
        } else {
            numberStack.push(num2 / num1);
        }
    }

    private static String format(String expression) {
        StringBuilder sb = new StringBuilder();
        //   " ( 10 + 20 / 2 * 3 )  / 2 + 8"
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')') {
                sb.append(' ');
                sb.append(c);
                sb.append(' ');
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
